package linkedList;

/**
 * 基于int的单链表
 */
public class SingLinkedList {
      private Node head;  //头节点
      private int size;   //保存的有效元素个数

    /**
     * 向当前链表中添加一个新的节点，默认是在头部添加
     * @param val
     */
    public void addFirst(int val) {
     Node  newNode=new Node();  //每增加一个节点就要创建新的Node类对象
     newNode.val=val;    //保存值
        if (head==null){
            head=newNode;  //此时链表为空，则增加的第一个值就是头节点

        }else  //此时链表不为空
        {
            newNode.next=head;  //先让新节点的引用指向头节点
            head=newNode;   //然后让head等于newNode

        }size++;   //增加链表长度，即为有效元素加一
    }

    /**
     * 移除链表中所有值为val的元素
     * @param val
     */
    public void removeAllVal(int val){
        while(head!=null&&head.val==val){
            //此时头节点就是待删除的点
            Node x=head;
            head=head.next;
            x=null;
        }
        //此时头节不是待删除点
        if (head==null){
            //假如第一步链表删空了
            return;
        }else{
            //此时待删除的时中间节点，需要遍历
            Node prev=head;
            while (prev.next!=null){
                //保证至少有后继节点
                if (prev.next.val==val){
                    //此时prev.next就是待删除点
                    Node node=prev.next;
                    prev.next=node.next;
                    node.next=null;
                    size--;
                }else{
              //只有当prev.next.val!=val才可以移动prev
                prev=prev.next;
            }


        }
        }
    }


    /**
     * 删除链表中第一个值为val的节点
     * @param val
     */
     public void removeOnce(int val){
         if (head==null){
             System.err.println("链表为空，无法删除");
             return;
         }
        if (head.val==val){
            //此时头节点就是待删除的节点
            Node x=head;
            head=head.next;
            x.next=null;
            size--;
        }else{
            //此时待删除的时中间节点，需要遍历
            Node prev=head;
            while (prev.next!=null){
                //保证至少有后继节点
                if (prev.next.val==val){
                    //此时prev.next就是待删除点
                    Node node=prev.next;
                    prev.next=node.next;
                    node.next=null;
                    size--;
                    return;
                }
                prev=prev.next;
            }

        }
   }

    /**
     * 删除索引为index的元素,返回删除前的元素值
     * @param index
     * @return
     */
    public int remove(int index){
       if (judge(index)){
             if (index==0){
                 //删除头节点
                 Node x=head;
                 head=head.next;
                 size--;
                 x.next=null;
                 return x.val;
             }else{
                 //删除中间节点
                 Node prev=head;
                 for (int i = 0; i <index-1; i++) {
                     prev=prev.next;
                 }
                 //prev就是待删除节点的前驱
                 //node就是待删除节点
                 Node node=prev.next;
                 prev.next=node.next;
                 node.next=null;
                 size--;
                 return node.val;
             }

       }
        System.err.println("index不在范围内");
       return -1;
    }

    /**
     * 修改索引为index位置的元素为newVal，并且返回修改前的值
     * @param index
     * @param newVal
     * @return
     */
    public int set(int index,int newVal){
        if (judge(index)){
            Node x=head;
            for (int i = 0; i <index ; i++) {
                x=x.next;
            }
            int oldVal=x.val;
            x.val=newVal;
            return oldVal;
        }
        System.err.println("index不在范围内");
        return -1;
    }


    /**
     * 查询索引为index位置的元素值
     * @param index
     * @return
     */
    public int get(int index){
        if (judge(index)){
            Node x=head;
            for (int i = 0; i <index; i++) {
                x=x.next;
            }return x.val;

        }
        return -1;
    }
    /**
     * 判断index是否合法，及是否在范围内
     * @param index
     * @return
     */
    private boolean judge(int index) {
        //注意此时的index不能取到size，size是有效元素的下一个索引
        if (index<0||index>=size){
            return false;
        }return true;
    }


    /**
     * 查找是否包含值为val的节点
     * @param val
     * @return
     */
    public boolean contains(int val){
        int index=getVal(val);
        if (index==-1){
            return false;
        }return true;
    }
    
    /**
     * 查询第一个值为val的元素的索引
     * @param val
     * @return
     */
    public int getVal(int val){
        int index=0;
        for (Node x=head;x != null;x=x.next) {
            if (x.val==val){
                //找到第一个值为val的元素
                return index;
            }index++;
        }return -1;
    }

    /**
     *在尾部插入新元素val
     * @param val
     */
   public void addLast(int val){
        add(size,val);
   }

    /**
     * 在链表的index位置插入新元素val
     * @param index
     * @param val
     */
    public void add(int index,int val){
        //判断index是合法
        //注意此时的index可以等于size，就相当于尾插
        if (index<0||index>size){
            System.out.println("index不在范围内");
            return;
        }
        //当给头节点插入时，有节点时没有前驱的
        if (index==0){
            addFirst(val);
        }else {
            Node newNode=new Node();
            newNode.val=val;
            //当前索引合法合法且不在头部插入，找待插入节点的前驱
            //让prev从头开始走index-1就刚好到前驱位置
            Node prev=head;
            for (int i = 0; i <index-1; i++) {
                prev=prev.next;
            }
            //此时prev指向了待插入节点的前驱
            newNode.next=prev.next;
            prev.next=newNode;
            size++;
        }
    }

    /**
     * 链表的打印
     * @return
     */
    public String toString(){
        String ret="";
        Node x=head;
        while(x!=null){
            ret += x.val;
            ret  += "->";
            x=x.next;
        }
        ret+="null";
        return ret;
    }


}




/**
 *单链表中具体的每个节点，即为车厢
 */
class Node{

    int val; //每个节点保存的值
    Node next;  //当前节点打的下一个节点地址

    public Node(){}

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}